Various embodiments of this disclosure relate to computer memory management and, more particularly, to set selection of a set-associative storage container.
Computer processing systems typically include one or more levels of cache memory to more quickly retrieve data relative to larger storage areas that are relatively slower to access, such as main memory. Some cache designs are partitioned into set-associative congruence classes to support address mapping, where cached data can be assigned to one of N set locations within a congruence class (N-way set associative, where each cache row is a congruence class of N sets). Such a cache is an example of a set-associative storage container. As another example, a set-associative storage container can be used for performance reasons as part of a processing pipeline.
When data is to be written into a particular congruence class of a set-associative storage container, a method must be employed to select one of the sets to write. The method used depends on the specific nature of the data and the mechanism the set-associative storage container is used for. Least recently used (LRU) is one example of a set marking and selection method, which generally offers the best performance, but at the cost of substantial logic to maintain and update the LRU state. Another less costly method, but not as high in performance, is a pseudo-LRU. In some instances, randomly or pseudo-randomly selecting a set can be appropriate, such as for a set-associative storage container that is used for maintaining performance data that exhibits volatile behavior (e.g., the data stored may help performance in most cases, and in others, hurt performance).
When one or more sets of a set-associative storage container are faulty, it can be challenging to maintain well balanced use of the non-faulty sets. One approach is to create logic that sequentially rotates through the non-faulty sets; however, such an approach becomes very complex when dealing with the possibility of multiple faulty sets.